Nearest neighbor (NN) searching is used in various applications, including computer vision, pattern recognition, and object detection. A goal of NN searching is to find, for a given search or query point, the closest data point, in terms of Euclidian distance, among a population of data points in a reference data set. A set of vectors represents all of the possible Euclidean distances. A variant of the basic NN search is the k-NN search, in which the “k” closest vectors are found for a given query point. Alternatively, an Approximate NN (ANN) search finds a vector that is approximately as close to the query point as the closest vector.
The data points examined via NN searching techniques may be, by way of example, visual or other patterns used in object detection. Thus, NN searching is fundamental to the execution of a multitude of different pattern recognition tasks. Examples in the field of computer vision include object detection and image retrieval. In a relatively high-dimensional space, finding an exact solution requires many vector comparisons and, as a result, computation may be relatively slow when using conventional NN searching techniques.
Existing methods for increasing the speed of basic NN searching include the use of k-dimensional (KD)-Trees, Randomized KD-Trees, and Hierarchical K-means. KD-Trees in particular provide a type of space-partitioning data structure for organizing points of interest in a given dimensional space. In a typical KD-Tree algorithm, a binary tree is created in which every node of the tree has a splitting dimension and a splitting threshold. A given root cell within a dimensional space is split into two sub-cells, with the sub-cells in turn split into two more sub-cells, until no more splitting occurs. The final cells are referred to as “leaf cells”. Using NN searching techniques, points on a KD Tree can be found that are nearest to a given input point, with the use of the KD Tree eliminating significant areas of the dimensional space and thus reducing the search burden. However, search speeds possible by KD-Trees and other approaches may remain less than optimal.